package com.sicheng.lc.杂题.滑动窗口专题;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/13 10:27
 */
public class 滑动窗口中位数_对顶堆 {
    // 以此题来了解对顶堆的原理
    // 里面有懒删除操作，和线段树里面的lazy标记类似
    // 堆里涉及到元素过期，等到过期元素浮上堆顶才物理pop。在浮上堆顶之前逻辑上认为这个元素被删了
    //  大致原理
    //  维护一个small (大顶对)，big(小顶堆)
    //  小的元素加入small，大的元素加入big. 用balance维护2个堆的平衡。也就是-1<=small.size()-big.size()<=1
    //  在初始情况下对顶堆已经是平衡的(实际上balance也许不是0)  就假设balance=0 开始计算平衡度
    //  窗口右移是需要淘汰和新增元素
    //  if l <=small.top()  balance--  else balance++
    //  if nums[r]<=small   balance++  else balance--
    //  窗口移动 只会造成 balance不变或者 balance==-2 or 2
    //https://leetcode.cn/problems/sliding-window-median/solution/feng-xian-dui-chong-shuang-dui-dui-ding-hq1dt/

    static PriorityQueue<Integer> small = new PriorityQueue<>((int) 1e3, Comparator.reverseOrder());
    static PriorityQueue<Integer> big = new PriorityQueue<>((int) 1e3);
    static HashMap<Integer, Integer> map = new HashMap<>(5000);

    {
        map.clear();
        small.clear();
        big.clear();
    }

    double getMid(int k) {
        if ((k & 1) == 0) {
            return (big.peek().doubleValue() + small.peek().doubleValue()) / 2;
        }
        return small.peek().doubleValue();
    }

    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] res = new double[nums.length - k + 1];
        for (int i = 0; i < k; i++) {
            small.offer(nums[i]);
        }
        for (int i = 0; i < k >> 1; i++) {
            big.offer(small.poll());
        }
        res[0] = getMid(k);
        for (int i = k; i < nums.length; i++) {
            int balance = 0;
            int l = nums[i - k];
            map.put(l, map.getOrDefault(l, 0) + 1);
            // 逻辑淘汰窗口左边界
            if (!small.isEmpty() && l <= small.peek()) {
                balance--;
            } else {
                balance++;
            }

            // 添加元素
            if (!small.isEmpty() && nums[i] <= small.peek()) {
                balance++;
                small.offer(nums[i]);
            } else {
                big.offer(nums[i]);
                balance--;
            }

            // 重新维护堆的平衡
            if (balance < 0)
                small.offer(big.poll());
            if (balance > 0)
                big.offer(small.poll());
            // 物理删除淘汰的所有过期的堆顶元素
            int out;
            while (!small.isEmpty() && (out = map.getOrDefault(small.peek(), 0)) > 0) {
                map.put(small.peek(), out - 1);
                small.poll();
            }
            while (!big.isEmpty() && (out = map.getOrDefault(big.peek(), 0)) > 0) {
                map.put(big.peek(), out - 1);
                big.poll();
            }

            // 生成结果
            res[i - k + 1] = getMid(k);
        }

        return res;
    }

    public static void main(String[] args) {
        滑动窗口中位数_对顶堆 s = new 滑动窗口中位数_对顶堆();
        int[] nums = {
                -2147483648, -2147483648, 2147483647, -2147483648,
                -2147483648, -2147483648, 2147483647, 2147483647,
                2147483647, 2147483647, -2147483648, 2147483647, -2147483648};
        System.out.println(Arrays.toString(s.medianSlidingWindow(nums, 3)));
    }

}
